package com.cj.startup.sort

import com.cj.startup.Startup
import com.cj.startup.StartupSortStore
import java.lang.RuntimeException
import java.util.ArrayDeque

class TopologySort {
    companion object{
        fun sort(startupList: MutableList<out Startup<*>>):StartupSortStore{
            //入度表，本Startup依赖了几个Startup
            val inDegreeMap = mutableMapOf<Class<out Startup<*>>,Int>()
            //0度表，没有任何依赖的Startup
            val zeroDeque = ArrayDeque<Class<out Startup<*>>>()
            //原图任务表
            val startupMap = mutableMapOf<Class<out Startup<*>>,Startup<*>>()
            //任务依赖表，第一个泛型是父（依赖）Startup，第二个泛型是所有依赖父Startup的子Startup
            val startupChildMap = mutableMapOf<Class<out Startup<*>>,MutableList<Class<out Startup<*>>>>()

            //1.找出图中入度数为0的节点，填表的过程
            startupList.forEach { startup ->
                val clazz = startup.javaClass
                checkRepeatedReference(startupMap,clazz)
                //原图任务表
                startupMap[clazz] = startup
                val dependenciesCount = startup.getDependenciesCount()
                inDegreeMap[clazz] = dependenciesCount
                if(dependenciesCount == 0){
                    //加入0度表，该Startup不依赖任何Startup
                    zeroDeque.offer(clazz)
                }else{
                    //该Startup有依赖，获取父（依赖）Startup，并将其加入到父任务依赖表中
                    startup.dependencies()?.forEach { parentClazz->
                        checkCycleDetected(startup,parentClazz,startupChildMap)
                        var startChildList = startupChildMap[parentClazz]
                        if(startChildList == null){
                            startChildList = mutableListOf()
                            startupChildMap[parentClazz] = startChildList
                        }
                        startChildList.add(startup.javaClass)
                    }
                }

            }

            //2.删除图中入度为0的这些顶点，并更新全图，最后完成排序
            val result = mutableListOf<Startup<*>>()
            val mainResult = mutableListOf<Startup<*>>()//工作在主线程的任务
            val threadResult = mutableListOf<Startup<*>>()//工作在子线程的任务

            //处理入度为0的任务
            while (zeroDeque.isNotEmpty()){
                val clazz = zeroDeque.poll()
                val startup = startupMap[clazz]?:continue
                if(startup.callCreateOnMainThread()){
                    mainResult.add(startup)
                }else{
                    threadResult.add(startup)
                }

                //删除此入度为0的任务
                if(startupChildMap.containsKey(clazz)){
                    val childStartup = startupChildMap[clazz]
                    childStartup?.forEach { childClazz->
                        //获取其入度数
                        val num = inDegreeMap[childClazz]?:1
                        //父Startup已排序，将子Startup的入度数减1，等待排序
                        val inNum = num - 1
                        inDegreeMap[childClazz] = inNum
                        if(inNum == 0){
                            //如果依赖的Startup都已排序，就轮到自己进行排序入列
                            zeroDeque.offer(childClazz)
                        }
                    }
                }
            }

            //工作在子线程的任务排在前面执行(就是将任务丢进线程池)，但是该任务会被await，只有当CountDownLatch的值为0的时候才能真正的执行
            result.addAll(threadResult)
            //工作在主线程的任务后执行，需要把所有工作在子线程的任务都放入线程池后才能来执行主线程的任务，否则主线程任务执行的时候，
            //不依赖主线程的任务并且需要在子线程执行的任务得不到执行
            result.addAll(mainResult)

            //返回排序后的结果
            return StartupSortStore(result, startupMap, startupChildMap)
        }

        private fun checkRepeatedReference(startupMap: MutableMap<Class<out Startup<*>>,Startup<*>>,clazz:Class<Startup<*>>){
            if(startupMap.containsKey(clazz)){
                throw RuntimeException("Startup被重复添加，${clazz}只能添加一次")
            }
        }

        private fun checkCycleDetected(
            startup: Startup<*>,
            parentClazz: Class<out Startup<*>>,
            startupChildMap: MutableMap<Class<out Startup<*>>, MutableList<Class<out Startup<*>>>>
        ) {
            val startupClazz = startup.javaClass
            startupChildMap[startupClazz]?.forEach { clazz ->
                if(clazz == parentClazz){
                    throw RuntimeException("Startup任务不能循环依赖，${startupClazz}与${parentClazz}存在循环依赖")
                }
            }

        }
    }
}